package org.ymx.myArrayList.algorithm;

import java.util.Arrays;

/**
 * @author 17122
 */
public class SortAlgorithm {

    /**
     * 冒泡排序
     *
     * @param array 将要被排序的数组
     * @return 排序完成的数组
     */
    public static int[] bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
        return array;
    }

    /**
     * 选择排序
     *
     * @param array
     * @return
     */
    public static int[] selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            //标记第一个为待比较的数
            int index = i;
            //然后从后面遍历与第一个数比较
            for (int j = i + 1; j < array.length; j++) {
                //如果小,就交换最小值
                if (array[j] < array[index]) {
                    //保存最小元素的下标
                    index = j;
                }
            }
            //找到最小值后，将最小的值放到第一的位置，进行下一遍循环
            int temp = array[index];
            array[index] = array[i];
            array[i] = temp;
        }
        return array;
    }

    /**
     * 插入排序
     *
     * @param array
     * @return
     */
    public static int[] insertSort(int[] array) {
        //长度不减1，是因为要留多一个位置方便插入数
        for (int i = 0; i < array.length; i++) {
            //定义待插入的数
            int insertValue = array[i];
            //找到待插入数的前一个数的下标
            int insertIndex = i - 1;
            //拿a[i]与a[i-1]的前面数组比较
            while (insertIndex >= 0 && insertValue < array[insertIndex]) {
                array[insertIndex + 1] = array[insertIndex];
                insertIndex--;
            }
            array[insertIndex + 1] = insertValue;
        }
        return array;
    }

    /**
     * 希尔排序
     *
     * @param array
     * @return
     */
    public static int[] shellSort(int[] array) {
        for (int gap = array.length / 2; gap > 0; gap = gap / 2) {
            //将整个数组分为若干个子数组
            for (int i = gap; i < array.length; i++) {
                //遍历各组的元素
                for (int j = i - gap; j >= 0; j = j - gap) {
                    //交换元素
                    if (array[j] > array[j + gap]) {
                        int temp = array[j];
                        array[j] = array[j + gap];
                        array[j + gap] = temp;
                    }
                }
            }
        }
        return array;
    }


    /**
     * 快速排序（递归）
     * <p>
     * ①. 从数列中挑出一个元素，称为"基准"（pivot）。
     * ②. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
     * ③. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
     *
     * @param arr  待排序数组
     * @param low  左边界
     * @param high 右边界
     */
    public static int[] quickSort(int[] arr, int low, int high) {
        if (arr.length <= 0) {
            return arr;
        }
        if (low >= high) {
            return arr;
        }
        int left = low;
        int right = high;
        //挖坑1：保存基准的值
        int temp = arr[left];
        while (left < right) {
            //坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
            while (left < right && arr[right] >= temp) {
                right--;
            }
            arr[left] = arr[right];
            //坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
            while (left < right && arr[left] <= temp) {
                left++;
            }
            arr[right] = arr[left];
        }
        //基准值填补到坑3中，准备分治递归快排
        arr[left] = temp;
        quickSort(arr, low, left - 1);
        quickSort(arr, left + 1, high);
        return arr;
    }

    /**
     * @param a
     * @param left
     * @param right
     * @param temp
     */
    private static void mergesort(int[] a, int left, int right, int[] temp) {
        //分解
        if (left < right) {
            int mid = (left + right) / 2;
            //向左递归进行分解
            mergesort(a, left, mid, temp);
            //向右递归进行分解
            mergesort(a, mid + 1, right, temp);
            //每分解一次便合并一次
            merge(a, left, right, mid, temp);
        }
    }

    /**
     * @param a     待排序的数组
     * @param left  左边有序序列的初始索引
     * @param right 右边有序序列的初始索引
     * @param mid   中间索引
     * @param temp  做中转的数组
     */
    private static void merge(int[] a, int left, int right, int mid, int[] temp) {
        //初始i，左边有序序列的初始索引
        int i = left;
        //初始化j，右边有序序列的初始索引（右边有序序列的初始位置即中间位置的后一位置）
        int j = mid + 1;
        //指向temp数组的当前索引，初始为0
        int t = 0;

        //先把左右两边的数据（已经有序）按规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完成为止
        while (i <= mid && j <= right) {
            //如果左边有序序列的当前元素小于或等于右边的有序序列的当前元素，就将左边的元素填充到temp数组中
            if (a[i] <= a[j]) {
                temp[t] = a[i];
                t++;//索引向后移
                i++;//i后移
            } else {
                //反之，将右边有序序列的当前元素填充到temp数组中
                temp[t] = a[j];
                t++;//索引向后移
                j++;//j后移
            }
        }
        //把剩余数据的一边的元素填充到temp中
        while (i <= mid) {
            //此时说明左边序列还有剩余元素
            //全部填充到temp数组
            temp[t] = a[i];
            t++;
            i++;
        }
        while (j <= right) {
            //此时说明左边序列还有剩余元素
            //全部填充到temp数组
            temp[t] = a[j];
            t++;
            j++;
        }
        //将temp数组的元素复制到原数组
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            a[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }
    }

    public static void main(String[] args) {
        //int[] ints = bubbleSort(new int[]{5, 3, 1, 2, 4, 6, 7});
        //int[] ints = selectSort(new int[]{5, 3, 1, 2, 4, 6, 7});
        //int[] ints = insertSort(new int[]{5, 3, 1, 2, 4, 6, 7});
        //int[] ints = shellSort(new int[]{5, 3, 1, 2, 4, 6, 7});
        int[] ints = quickSort(new int[]{5, 3, 1, 2, 4, 6, 7}, 0, 6);
        for (int i : ints) {
            System.out.print(i + "   ");
        }
    }


}
